The present invention relates generally to network communications and data routing protocols. More particularly, the present invention relates to a dynamic next hop routing protocol and system for obtaining next hop data link addresses in wireless networks.
Wireless communication networks incorporating one or more mobile devices have become increasingly widespread in recent years. Retail stores and warehouses, for example, may use communication networks with mobile data terminals to track inventory and replenish stock. The transportation industry may use such networks at large outdoor storage facilities to keep an accurate account of incoming and outgoing shipments. In manufacturing facilities, such networks are useful for tracking parts, completed products and defects. Such networks are also utilized in cellular telephone communications to allow users with wireless telephones to roam across large geographic regions while retaining telephonic access. Paging networks also utilize mobile communication networks which enable a user carrying a pocket sized pager to be paged anywhere within a geographic region.
Conventional wireless communication networks such as those referred to above typically involve a cellular network. As is known, cellular networks includes a number of fixed access points (also known as base stations) interconnected by a cable medium often referred to as a system backbone. Associated with each access point is a geographic cell. Such cell is a geographic area in which an access point has sufficient signal strength to transmit data to and receive data from a mobile device such as a data terminal or telephone with an acceptable error rate. Typically, access points will be positioned along the backbone such that the combined cell area coverage from each access point provides full coverage of a building or site.
Mobile devices such as telephones, pagers, personal digital assistants (PDAs), data terminals, etc. are designed to be carried throughout the system from cell to cell. Each mobile device is capable of communicating with the system backbone via wireless communications between the mobile device and an access point to which the mobile device is registered. As the mobile device roams from one cell to another, the mobile device will typically deregister with the access point of the previous cell and register with the access point associated with the new cell.
In order to provide sufficient cell area coverage, access points within the cellular communication system typically are distributed at separate physical locations throughout an entire geographical region. Unfortunately, this can lead to high costs since access points are relatively expensive compared to the mobile devices. Also, if an access point fails it can result in an entire cell being xe2x80x9cblacked outxe2x80x9d from communications with other devices within the network.
In view of shortcomings such as those discussed above, there is a strong need in the art for a mobile communication network and protocol which enables communications between mobile and fixed devices even in the absence of access points. In particular, there is a strong need in the art for a mobile communication network and protocol which provides for mobile devices to serve both as ultimate data sources and destinations, as well as routers for routing data to its destination.
The present invention provides a network in which mobile devices themselves serve as routers of data packets. Each mobile device represents a node in the network. The nodes advertise a list of nodes which are reachable through their interface(s). When a node receives a data packet for which it is not the ultimate destination, it looks up a next hop link address from its list of reachable nodes, and forwards the data packet to that address.
According to one aspect of the invention, in a wireless network having a plurality of nodes which roam about the network, a method for routing data packets among the nodes is provided whereby at least one node carries out the steps of: maintaining a list of nodes which are reachable through the node based on communication received from other nodes; and when receiving data for which the node is not the ultimate destination, attempting to forward the data towards the ultimate destination based on the list of nodes.
According to another aspect of the invention, in a wireless network having a plurality of nodes which roam about the network, a method for routing data packets among the nodes is provided whereby each of the nodes carries out the steps of: maintaining a list of nodes which are reachable through the node based on advertisements received from other nodes; advertising to other nodes the list of nodes which are reachable through the node; and when receiving data for which the node is not the ultimate destination, forwarding the data towards the ultimate destination based on the list of nodes.
According to still another aspect of the invention, a method of communicating routing information in a cellular communication system is provided, the method including the steps of: receiving at a first mobile node communication from a second mobile node operating within direct communication range; adding the second mobile node to a routing table maintained by the first mobile node; and transmitting from the first mobile node, for receipt by at least one other mobile node which may be operating within direct communication range of the first mobile node, at least a portion of the routing table including information related to the second mobile node.
According to another aspect of the invention, a mobile node capable of routing information in a cellular communication system is provided, the mobile node including; wireless communication means for communicating information between the mobile node and any other reachable node; means for maintaining a list of nodes which are reachable through the mobile node based on communication wirelessly received from the other nodes; and means for attempting to wirelessly forward data received towards the ultimate destination based on the list of nodes when the mobile node is not the ultimate destination for the data received.
According to yet another aspect of the invention, a network communication system is provided, including; a backbone; a plurality of base stations coupled to the backbone; a plurality of mobile nodes communicating with the backbone via the base stations; wherein at least one of the mobile nodes includes: wireless communication means for communicating information between the mobile node and any other reachable node; means for maintaining a list of nodes which are reachable through the mobile node based on communication wirelessly received from other nodes; and means for attempting to wirelessly forward data received towards the ultimate destination based on the list of nodes when the mobile node is not the ultimate destination for the data received.